//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 👍 4575 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _4_MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{3,4};
        Solution solution = new _4_MedianOfTwoSortedArrays().new Solution();
        double res = solution.findMedianSortedArrays(nums1, nums2);
        System.out.println(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 把第一个数组设置为小数组
            if (nums1.length > nums2.length) {
                int[] temp = nums1;
                nums1 = nums2;
                nums2 = temp;
            }

            int m = nums1.length;
            int n = nums2.length;

//            int totalLeft = (m + n + 1) / 2;
            int totalLeft = m + (n - m + 1) / 2; // 为了防止整型溢出

            int start = 0;
            int end = m;

            while (start < end) {
                int i = start + (end - start + 1) / 2;
                int j = totalLeft - i;
                if (nums1[i - 1] > nums2[j]) {
                    // 下一轮搜索区间[start, i-1]
                    end = i - 1;
                } else {
                    // 下一轮搜索区间[i, end]
                    // [start(i), end] 会死循环，所以要给i+1
                    start = i;
                }
            }

            int i = start;
            int j = totalLeft - i;

            int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
            int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

            if (((m + n) % 2) == 1) {
                return Math.max(nums1LeftMax, nums2LeftMax);
            } else {
                return  ((double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2);
            }
        }

        public double findMedianSortedArrays_myself(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int[] nums = new int[m + n];
            int j = 0;
            int k = 0;
            for (int i = 0; i < m + n; i++) {
                int n1 = j == m ? 1000001 : nums1[j];
                int n2 = k == n ? 1000001 : nums2[k];
                nums[i] = n1 < n2 ? nums1[j++] : nums2[k++];

            }
            System.out.println(Arrays.toString(nums));

            int len = nums.length;
            if (len % 2 == 1) {
                return (double) nums[(len - 1) / 2];
            } else {
                return ((double) nums[len / 2 - 1] + (double) nums[len / 2]) / 2;
            }

//        System.out.println(2^3);

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}